package leetcode.hot100;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class Solution739 {

    public static void main(String[] args) {
        int[] temp = new int[]{73, 74, 75, 71, 69, 72, 76, 73};
        int[] ints = new Solution739().dailyTemperatures(temp);
        System.out.println(Arrays.asList(ints));
    }

    public int[] dailyTemperatures(int[] temperatures) {
        //单调减栈，入栈前把小于要入栈的元素全部出栈
        int n = temperatures.length;
        Deque<Integer> descStack = new LinkedList<Integer>(); //用来记录当前入栈的元素下标
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            while (descStack.size()>0&&temperatures[descStack.peek()]<temperatures[i]){
                int curPop = descStack.pop();
                res[curPop] = i - curPop;
            }
            descStack.push(i);
        }
        return res;
    }
}
